package _543cloud_new;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;

public class Calculator {
	
	//capacity, index
	HashMap<Integer, Integer> index = new HashMap<>();
	int[] input;
	int sum;
	int[] ret_index;

	public Calculator(){
		
	}
	
	public int[] getresult(){
		return ret_index;
	}
	public Calculator(int[] num, int n){
		this.input = num;
		this.sum = n;
		for(int i=0;i<num.length;i++){
			index.put(num[i], i);
		}
		ret_index = getindex(input, sum);
//		ret_index = solutionD(input, sum);
	}
	
	public int[] getindex(int[] num, int n){
		int flag = n;
		int[] to_return = null;
		int[] temp = equal(num, flag);	
		while(true){
			if(getsum(temp) == flag){
				to_return = new int[temp.length];
				for(int i=0;i<temp.length;i++){
					to_return[i] = index.get(temp[i]);
				}
				return to_return;
			}
			else{
				temp = equal(num, ++flag);
				if(flag>getsum(num)) return null;
			}
		}	

	}
	
	public int getsum(int[] input){
		int to_return = 0;
		for(int i=0;i<input.length;i++)
			to_return+=input[i];
		return to_return;
	}
	
	public int[] equal(int[] array, int s){
		//因为需要初始化，所以把行列都加1
		Node[][] mx = new Node[array.length+1][s+1];
		for(int i = 0; i<mx.length;i++){
			for(int j = 0; j<mx[0].length; j++){
				//因为把行列都加1,所以第一行第一列都是0				
				if(i==0 || j==0){
					mx[i][j] = new Node(0, 0, null);
					continue;
				}
				//取出当前数组里的数以及上一个和的节点
				int w = array[i-1];
				Node dNode = mx[i-1][j];
				//如果当前值直接大于要找的，选当前
				if(w > j)
					mx[i][j] = new Node(0,dNode.max, dNode);
				//否则
				else{
					Node tempN = mx[i-1][j-w];
					//如果这次要的值减去w的节点的值加上这次的值直接大于这次需要的值，用j－w和这次的取代
					if(tempN.max + w > dNode.max)
						mx[i][j] = new Node(w,tempN.max+w,tempN);
					//否则延用上一个背包
					else
						mx[i][j] = new Node(0, dNode.max, dNode);			
				}
			}
		}	
		ArrayList<Integer> result = new ArrayList<>();
		//每个node的next联通的是它上一个背包，比如10＝5＋3＋2, 5－>3->2，因为每次递增1,判断条件都是大于
		//所以不直接选取4,而去选3,sulotionD里的方法更加直白
		Node node = mx[array.length][s];
		while(node!=null){
			if(node.val>0)
				result.add(node.val);
			node = node.next;
		}
		
		int[] to_return = new int[result.size()];
		for(int i=0;i<result.size();i++){
			to_return[i] = result.get(i);
		}	
		//直接返回每个的值，上面有一个叫index的hashmap来记录每个值对应的坐标，
		//如果有重复的值返回这个值得任意坐标，因为选哪个都是一样的
		return to_return;	
	}


	
	private class Node{	
		int val;
		int max;
		Node next;
		
		public Node(int val, int max, Node next){
			this.val = val;
			this.max = max;
			this.next = next;
		}
	}
	
	public static int[] solutionD(int[] input, int sum) {
        int[] ret = solutionD(input, sum, 0);
        if (ret == null) {
            return null;
        }
        int[] result = Arrays.copyOfRange(ret, 1, ret.length);
        Arrays.sort(result);
        return result;
    }

    public static int[] solutionD(int[] input, int sum, int start) {
        if (sum <= 0) {
            return new int[] {0};
        }
        if (start >= input.length) {
            return null;
        }
        int[] min_ret = null;
        int min_sum = 0;
        int next_index = 0;
        for (int i = start; i < input.length; i ++) {
        	//进行交换，每次把当前数组的第一个和之后每一个进行交换
            int temp = input[start];
            input[start] = input[i];
            input[i] = temp;
            //这里，选取当前交换以后的点，并且递归计算剩下的数组
            int[] ret = solutionD(input, sum - input[start], start + 1);
            if (ret != null) {
                int s = ret[0] + input[start];
                if (min_ret == null || min_sum > s ||
                   (min_sum == s && ret.length < min_ret.length)) {
                		//这里的大概思路相当于把数组全排列，每次选择前k个数和>=指定值
                		//并用ret返回上一层递归，如果ret的数量不小于用来记录的数组min_ret的数量，
                		//将不进行操作，因为要求要最少的
                		min_sum = s;
                		min_ret = ret;
                		next_index = i;
                		for (int j = 1; j < min_ret.length; j ++) {
                			if (min_ret[j] == i) {
                				min_ret[j] = start;
                			}
                		}
                }
            }
            //交换回来并返回递归的上一层
            temp = input[start];
            input[start] = input[i];
            input[i] = temp;
        }
        if (min_ret == null) {
            return null;
        }
        int[] result = new int[min_ret.length + 1];
        result[0] = min_sum;
        result[1] = next_index;
        for (int j = 1; j < min_ret.length; j++) {
            result[1+j] = min_ret[j];
        }
        return result;
    }
	
	
	
	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		int[] test = {4,3,2,1,5};
		Calculator ca = new Calculator(test,10);
//		int[] ret = ca.getresult();
		int[] ret = ca.solutionD(test, 10);
		for(int i=0;i<ret.length;++i){
			System.out.println(ret[i]);
		}
		
	}
	
}
